Steven_Meng's Blog

传送门

这题其实有两种做法：

$1.$
我一开始想到的是二分加并查集，考虑二分最近部落的距离，如果两点$i$，$j$距离小于等于$mid$那么连边，并查集维护，最后统计有多少集合。
考虑如何证明单调性：如果两点$i$，$j$在$mid1$情况下能连边，那么在$mid2$情况下也能连边（$mid2>mid1$），那么$mid1$情况下的集合数不可能小于$mid2$情况下的集合数
这样我们可以愉快地二分答案。

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
    int fa[MAXN];
    inline void Init(){
        for (register int i=0;i<MAXN;++i){
            fa[i]=i;
        }
    }
    int Fa(int i){
        return fa[i]==i?i:fa[i]=Fa(fa[i]);
    }
    inline void Union(int i,int j){
        fa[Fa(i)]=Fa(j);
    }
};
using namespace BCJ;
int x[MAXN],y[MAXN];
inline double Dist(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int n,k;
inline bool Check(double mid){
    Init();
    for (register int i=1;i<=n;++i){
        for (register int j=1;j<=n;++j){
            if (Dist(i,j)<=mid){
                Union(i,j);
            }
        }
    }
    int ans=0;
    for (register int i=1;i<=n;++i){
        if (fa[i]==i) ans++;
    }
    return ans>=k;
}
int main(){
    Init();
    n=read(),k=read();
    for (register int i=1;i<=n;++i){
        x[i]=read(),y[i]=read();
    }
    double l=0,r=0x7fffffff;
    const double eps=1e-4;
    while (l+eps<r){
        double mid=(l+r)/2.0;
        if (Check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n",l);
}

$2.$
考虑连边过程中集合数的变化，发现多连一条边，集合数就会减一。
要让最后有$k$个集合，$yy$一下，发现要连$n-k+1$条边，于是我们可以用一个类似于$Kruskal$的贪心，只不过加到$n-k+1$条边就退出。

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
    int fa[MAXN];
    inline void Init(){
        for (register int i=0;i<MAXN;++i){
            fa[i]=i;
        }
    }
    int Fa(int i){
        return fa[i]==i?i:fa[i]=Fa(fa[i]);
    }
    inline void Union(int i,int j){
        fa[Fa(i)]=Fa(j);
    }
};
using namespace BCJ;
struct Edge{
    int u,v;
    double w;
}G[MAXN*2];
inline bool operator < (const Edge &A,const Edge &B){
    return A.w<B.w;
}
int tot;
inline void AddEdge(int u,int v,double w){
    G[++tot].u=u,G[tot].v=v,G[tot].w=w;
}
double x[MAXN],y[MAXN];
#define Pow(a) a*a
inline double dis(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
inline double Kruscal(int MaxE){
    Init();
    sort(G+1,G+1+tot);
    int E=0;
    for (register int i=1;i<=tot;++i){
        if (Fa(G[i].u)!=Fa(G[i].v)){
            Union(G[i].u,G[i].v);
            E++;
            if (E==MaxE){
                return G[i].w;
            }
        }
    }
}
int main(){
    int n=read(),k=read();
    for (register int i=1;i<=n;++i){
        x[i]=(double)read();
        y[i]=(double)read();
    }
    for (register int i=1;i<n;++i){
        for (register int j=i+1;j<=n;++j){
            AddEdge(i,j,dis(i,j));
        }
    }
    printf("%.2lf\n",Kruscal(n-k+1));
}

p.s被$double$孙了甚久。